public class test {
    //leetcode 879.盈利计划
    class Solution {
        // 三维解法(二维费用 + 遍历员工) -> 01背包
        public int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
            // 1. 创建 dp 表
            int len = group.length;
            int mod = (int)1e9 + 7;
            //第 i 种工作时,使用的员工小于 j 并且创造利润大于 k 的计划个数
            int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
            // 2. 初始化
            dp[0][0][0] = 1;
            // 3. 填表
            for(int i = 1;i <= len;i++){
                //需要工人
                int num1 = group[i - 1];
                //产生利润
                int num2 = profit[i - 1];
                for(int j = 0;j <= n;j++){
                    for(int k = 0;k <= minProfit;k++){
                        //如果 j < num1 则代表工人不足,无法选择该种工作
                        if(j < num1){
                            dp[i][j][k] = dp[i-1][j][k];
                        }else {
                            //如果 k < num2 则代表单单是此种工作,盈利就已经大于所需的 k
                            //直接用它加上上一个工作中最多的计划数量(k = 0)
                            //如果 k >= num2 则模仿01背包模板,寻找符合条件最大值即可
                            if(k < num2){
                                dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-num1][0]) % mod;
                            }else {
                                dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-num1][k-num2]) % mod;
                            }
                        }
                    }
                }
            }
            // 4. 返回值
            int sum = 0;
            for(int i = 0;i <= n;i++){
                sum = (sum + dp[len][i][minProfit]) % mod;
            }
            return sum;
        }
        // 二维解法(二维费用) -> 01背包空间优化
        public int profitableSchemes(int n, int minProfit, int[] group, int[] profit){
            int mod = (int)1e9 + 7;
            // 1. 创建 dp 表
            //工作种类个数
            int len = group.length;
            //第 i 种工作时,使用的员工小于 j 并且创造利润大于 k 的计划个数
            int[][] dp = new int[n+1][minProfit+1];
            // 2. 初始化
            for(int i = 0;i <= n;i++){
                dp[i][0] = 1;
            }
            // 3. 填表
            for(int i = 1;i <= len;i++){
                int num1 = group[i - 1];
                int num2 = profit[i - 1];
                for(int j = n;j >= num1;j--){
                    for(int k = minProfit;k >= 0;k--){
                        int num = 0;
                        if(num2 > k){
                            num = dp[j - num1][0];
                        }else {
                            num = dp[j - num1][k - num2];
                        }
                        dp[j][k] = (dp[j][k] + num) % mod;
                    }
                }
            }
            // 4. 返回值
            return dp[n][minProfit];
        }
    }
}
